/*
 * topological-hex, a program to compute combinatorial hexahedral meshes.
 *
 * Copyright (C) <2018> <Université catholique de Louvain (UCL), Belgique>
 *
 * List of the contributors to the development, description and complete
 * License: see LICENSE file.
 *
 * This program (topological-hex) is free software:
 * you can redistribute it and/or modify it under the terms
 * of the GNU General Public License as published by the Free
 * Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program (see COPYING file).  If not,
 * see <http://www.gnu.org/licenses/>.
 */

#ifndef DFS_H_
#define DFS_H_

#include "solver.h"

/**
 * @defgroup dfs Depth-first Search
 *
 * Tools to explore the search tree represinting all potential hex-meshes of the
 * input boundary.
 */

/**
 * @addtogroup dfs
 * @{
 */

/**
 * Searches for hexahedral mesh by exploring the entire search tree using a
 * depth-first search.
 *
 * @param cb Function called when a solution is found
 * @param user_data Pointer to arbitrary data. This value is passed to the
 *   callback whenever it is called.
 */
void solver_run(solver *solver, solver_callback cb, void *user_data);

/**
 * Data structure used to store changes made while traversing the tree. This is
 * used in order to reverse those changes when backtracking.
 */
typedef struct fixed_point_delta {
  /**
   * New entries that have been set to one in @ref solver::bound_mask.
   */
  uint32_t new_bound_mask;

  /**
   * Indices of the diagonal that have been created in this iteration.
   */
  uint32_t diagonal_mask;

  /**
   * Set of vertices removed from the domain of each variable.
   */
  ALIGNED vertex_set domain_changes[4];

  /**
   * Number of faces that have been completed in this iteration.
   */
  uint32_t num_occurrences_changes;

  /**
   * Number of new quads created in this iteration.
   */
  uint32_t max_quad_change;

  /**
   * Indices of the quads that have been added to this hexahedron.
   */
  quad_index occurred[5];

  /**
   * For each vertex v of the hexahedron, the set of vertices whose set
   * of allowed neighbors no longer contains v.
   */
  ALIGNED vertex_set removed_from[8];

  /**
   * Set of vertices that have been removed from the set of allowed neighbors of
   * each vertex.
   */
  ALIGNED vertex_set allowed_set_changes[8];

  /**
   * Set of new vertices that have been added to the set of known neighbor of
   * each vertex.
   */
  ALIGNED vertex_set new_neighbors[8];

  /**
   * Vertices that have been colored by the algorithm to ensure that the graph
   * it produces is bipartite.
   */
  vertex_set new_even_vertices, new_odd_vertices;
} fixed_point_delta;

/**
 * Propagates changes in order to prune the search space.
 *
 * Modifications performed by this function are stored in @p delta so that they
 * can be reversed using @ref undo_fixed_point:
 *
 * @code
 * if (fixed_point(solver, &delta)) {
 *    // more work
 * }
 * undo_fixed_point(solver, &delta);
 * @endcode
 *
 * @return True if there may still be solutions to the problem after propagating
 *   changes. False if the user should backtrack.
 */
bool fixed_point(solver *solver, fixed_point_delta *delta);

/**
 * Reverses the changes made by @ref fixed_point.
 */
void undo_fixed_point(solver *solver,
                      const fixed_point_delta *delta);

/**
 * Retrieves a quad that still needs to be added to one hexahedron.
 *
 * This operation can be reversed when backtracking by calling @ref
 * undo_pop_quad:
 *
 * @code
 * quad_index quad = pop_quad(solver, &delta);
 * if (quad == NO_QUAD)
 *   // found a solution
 * else
 *   // keep progressing
 * undo_pop_quad(solver, quad, &delta);
 * @endcode
 *
 * @param [out] delta_size Pointer used to store information necessary for
 *   backtracking purposes.
 *
 * @return The index of a quad that should be added to a hexahedron, or NO_QUAD
 *   if the queue is empty.
 */
quad_index pop_quad(solver *solver, uint32_t *delta_size);

/**
 * Reverses che changes made by @ref pop_quad.
 */
void undo_pop_quad(solver *solver, quad_index quad, uint32_t delta_size);

/**
 * Determines which variable the algorithm should branch on.
 *
 * The returned set may be smaller than the domain of the variable, for example
 * because this function returns at most one interior vertex that has not been
 * used yet, so as to break symmetry.
 *
 * @param [out] The set of value the branching variable can take.
 *
 * @return The index of the variable to branch on, or 4 if all variables are
 *   already bound.
 */
quad_vertex_index choose_variable(const solver *solver, vertex_set *domain);

/**
 * Explores the subtree described by @p solver.
 */
void choose_vertex(solver *solver);

/**
 * Mutates the solver until a branching point is reached.
 *
 * @return True If a branching point was found, false if a dead end (including a
 *   solution) was reached.
 */
bool propagate(solver *solver);

/**
 * @}
 */

#endif
